package problem5;

//5.最长回文子串
//https://leetcode.cn/problems/longest-palindromic-substring/description/

class Solution {
    public String longestPalindrome(String _s) {
        int n = _s.length();
        char[] s = _s.toCharArray();
        int[][] dp = new int[n][n];

        int ret = 0;
        int l = 0, r = 0; //记录最长回文子串的下标
        for(int i = n-1; i>=0; i--) {
            for(int j = i; j<n; j++) {
                if(i == j) dp[i][j] = 1;
                else if(s[i] == s[j] && i+1 == j) dp[i][j] = 2;
                else if(s[i] == s[j] && dp[i+1][j-1]!=0) dp[i][j] = dp[i+1][j-1] + 2;

                //更新结果
                if(ret < dp[i][j]) {
                    ret = dp[i][j];
                    l = i;
                    r = j;
                }
            }
        }

        return _s.substring(l, r+1);
    }
}

/*

dp[i][j]:以第i和第j个字符为结尾的最长回文子串
dp[i][j] == 0: i~j之间的字符串不是回文串

*/